1. Field of the Invention
The present invention relates generally to a method and system for processing data packets in switched communications networks and in particular to a method and a system for forwarding data packets in a router.
2. Description of the Prior Art
A switched communications network transfers data from source to destination through a series of network nodes. Switching can be done in one of two ways. In a circuit-switched network, a dedicated connection is established through the network and is held for as long as communication is necessary. An example of this type of network is the traditional telephone system.
A packet-switched network, on the other hand, routes data in small pieces called packets, each of which proceeds independently through the network. In a process called store-and-forward, each packet is temporarily stored at each intermediate node, then forwarded when the next link becomes available. In a connection-oriented transmission scheme, each packet takes the same route through the network, and thus all packets usually arrive at the destination in the order in which they were sent. Conversely, each packet may take a different path through the network in a connectionless or datagram scheme. Since datagrams may not arrive at the destination in the order in which they were sent, they are numbered so that the destination user can reorder them properly. Ideally, a network experiences no mutual interference between links, a standard that implies that several links can simultaneously carry packets between their respective transmitting and receiving nodes.
In the last decade the amount of data packet traffic being communicated over communication networks has grown exponentially. This applies especially to the Internet that is a well-known member of connectionless packet-switched networks. In some environments the data packet traffic has reached such an enormous amount that conventional routers reach their limit. Since the performance of a router is crucial to the number of packets that can be transmitted through a communication network or from one communication network to another, a slow router can cause a backlog of data packets. Hence, the data packets need more time to reach their destination.
A data packet is routed through the network primarily according to its destination address. In order to determine the correct subsequent network the router has to convert the destination address of a data packet into a corresponding next hop physical address (i.e. the outgoing port of a router). This task is called “address resolution” and is carried out as a part of the more complex “packet processing” task. The destination address is stored in a packet header. The packet header is a portion of a packet that is preceding the actual data, containing source and destination addresses, error checking and other fields.
Packet processing, in addition, includes carrying out tasks like classification, filtering or load balancing, which may, based on multiple fields contained in the packet (not only the destination address), further influence the “address resolution” and the entire treatment and alterations applied to the packet in a router. For example, decide on specific QoS (Quality of Service) treatment of the packet, its mapping onto an MPLS (Multiprotocol Label Switching) label, discarding it or sending it to a control point in case of filtering or splicing with another TCP (Transmission Control Protocol) connection in case of load balancing.
Packet processing is a resource intensive procedure that requires fast processors and instant memory access. In order to speed up performance of the packet processing more than one packet processing unit is normally provided within a router. Two different approaches have been followed in the architecture of routers to comply with the aforementioned requirements.
In a distributed router architecture, the packet processing is performed in a processing device located directly at each input port. After the conversion of the packet's destination address into a physical address the packet is forwarded towards the determined physical address, i.e., a corresponding output port. Although packets at different input ports can be processed simultaneously, the whole computing capability of all packet processing units might actually not be utilized in real live situations, since the incoming traffic load is hardly ever evenly distributed over all input ports or it does not always reach the line rate.
A parallel router architecture seeks to overcome this drawback. In the parallel router architecture a pool of packet processing units is accessible through a pool interconnect connecting all packet processing units and providing a link to the input ports. Through the pool interconnect the input ports have access to the pool of packet processing units that can process multiple packets concurrently. Thus, every packet from each input is submitted for processing to the pool of parallel packet processing units. That is, for each incoming packet a request for packet processing is sent to the pool of parallel packet processing units. After the packet is processed the respective information is sent back to the originating input port, from where the packet gets forwarded to determined output port. In the parallel router architecture, a bottleneck or a single point of failure for the whole device might become the pool interconnect or a load balancing device of the pool.